package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //解数独
        class Solution {
            boolean[][] rowVis, colVis;
            boolean[][][] grid;
            char[][] board;

            public void solveSudoku(char[][] _board) {
                rowVis = new boolean[9][10];
                colVis = new boolean[9][10];
                grid   = new boolean[3][3][10];
                board  = _board;

                // 预处理：把已填数字写入三张表
                for (int r = 0; r < 9; r++) {
                    for (int c = 0; c < 9; c++) {
                        if (board[r][c] != '.') {
                            int d = board[r][c] - '0';
                            rowVis[r][d] = true;
                            colVis[c][d] = true;
                            grid[r/3][c/3][d] = true;
                        }
                    }
                }
                solve(); // 回溯求解（题目保证唯一解）
            }

            // 回溯：寻找下一个空格，尝试 1..9
            private boolean solve() {
                for (int r = 0; r < 9; r++) {
                    for (int c = 0; c < 9; c++) {
                        if (board[r][c] == '.') {
                            for (int d = 1; d <= 9; d++) {
                                if (rowVis[r][d] || colVis[c][d] || grid[r/3][c/3][d]) continue;
                                // 选择
                                board[r][c] = (char) ('0' + d);
                                rowVis[r][d] = colVis[c][d] = grid[r/3][c/3][d] = true;

                                if (solve()) return true; // 向后成功，直接收敛

                                // 撤销
                                board[r][c] = '.';
                                rowVis[r][d] = colVis[c][d] = grid[r/3][c/3][d] = false;
                            }
                            // 该空格 1..9 全失败，触发回溯
                            return false;
                        }
                    }
                }
                // 未找到空格，说明已填满
                return true;
            }
        }

        //单词搜索
        class Solution2 {
            boolean[][] vis;
            char[][] board;
            String word;
            int[] dx = {1,-1,0,0};
            int[] dy = {0,0,1,-1};
            int m,n;
            StringBuffer path; // 保留你的风格，未使用

            public boolean exist(char[][] _board, String _word) {
                board = _board;
                word  = _word;
                path  = new StringBuffer();
                m = board.length;
                n = board[0].length;
                vis = new boolean[m][n];

                char ch = word.charAt(0);
                for(int i = 0; i < m; i++){
                    for(int j = 0; j < n; j++){
                        if(board[i][j] == ch){
                            vis[i][j] = true;                 // 起点进入：先标记
                            boolean flag = isExist(i, j, 1);  // pos=1，下一步去匹配 word[1]
                            if(flag) return true;
                            vis[i][j] = false;                // 起点失败：恢复
                        }
                    }
                }
                return false;
            }

            // 从 (row,col) 开始，去邻居匹配 word[pos]
            public boolean isExist(int row, int col, int pos){
                if (pos == word.length()) return true;  // 已匹配完整串

                char ch = word.charAt(pos);
                for(int k = 0; k < 4; k++){
                    int x = row + dx[k], y = col + dy[k];
                    if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && board[x][y] == ch){
                        vis[x][y] = true;                          // 进入子格：标记
                        boolean flag = isExist(x, y, pos+1);
                        if(flag) return true;                      // 命中直接返回
                        vis[x][y] = false;                         // 失败：回溯
                    }
                }
                return false; // 所有方向失败
            }
        }
    }
}